package com.itbaizhan;

import java.util.Arrays;

/**
 * 二分法查找(笔试可能会考)
 */
public class TestBinarySearch {
    public static void main(String[] args) {
        int[] arr = {30,20,50,10,80,9,7,12,100,40,8};
        int searchWord = 20;//查找的数
        Arrays.sort(arr);//二分法查找之前，一定要对数组元素排序

        System.out.println(Arrays.toString(arr));
        System.out.println(searchWord+"元素的索引："+binarySearch(arr,searchWord));

    }

    public static int binarySearch(int[ ] array, int value){
        int low = 0;
        int high = array.length-1;//由0开始计算，所以要-1
        while (low <= high){
            int middle = (low+high)/2;
            if (value == array[middle]) {
                return middle;  //返回查询到的索引位置
            }
            if (value > array[middle]) {
                low = middle+1;  //要查找的数大于中间数，最小的计数low向右走一格（+1），最大的计数不变
            }
            if(value < array[middle]){
                high = middle-1; //要查找的数小于中间数，最大的计数high向左走一格（-1），最小的计数不变
            }
        }
        return -1; //上面循环完毕，说明未找到，返回-1
    }
}
